package datastructure.list;

import java.lang.reflect.Array;
import java.util.Iterator;

/**
 * Description：带头结点和尾节点的双链表（非循环）
 * 头结点和尾节点均存储元素。
 * Author: zhangc
 * Date：2017/6/26 17:33
 */
public class LinkedList8<T> implements List<T> {

    private Node head;
    private Node last;
    private Integer size = 0;


    private class Node {
        private T value;
        private Node previous;
        private Node next;

        private Node(T value) {
            this.value = value;
        }
    }

    @Override
    public void append(T element) {
        if (size == 0)
            addFirst(element);
        else {
            Node temp = new Node(element);
            last.next = temp;
            temp.previous = last;
            last = temp;
            size++;
        }
    }

    private void addFirst(T value) {
        head = new Node(value);
        last = head;
        size++;
    }

    private void indexSafe(Integer index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("下标越界。。。");
    }

    @Override
    public void insert(int index, T element) {
        indexSafe(index);
        Node temp;
        Node insertNode = new Node(element);
        if (index == 0) {// 此处为在第一个位置前插入元素，考虑 链表 空和不空 两种情况
            if (size == 0) {
                addFirst(element);
                return;
            } else {
                insertNode.next = head;
                head.previous = insertNode;
                head = insertNode;
                size++;
                return;
            }
        }
        if (index > (size >> 1)) { // 当下标大于链表长度一半时，从后往前找
            temp = last;
            // 这里迭代的次数需要注意
            for (int i = 0; i < (size - index); i++) {
                temp = temp.previous;
            }
        } else { // 从前往后找
            temp = head;
            for (int i = 1; i < index; i++) {
                temp = temp.next;
            }
        }
        insertNode.previous = temp;
        insertNode.next = temp.next;
        temp.next = insertNode;
        size++;
    }

    @Override
    public T get(int index) {
        indexSafe(index);
        Node temp;
        // 这里做了一下优化,当下标大于长度的一半时，从后往前查找
        if (index > (size >> 1)) {
            temp = last;
            // 这里迭代的次数需要注意
            for (int i = 1; i < (size - index); i++) {
                temp = temp.previous;
            }
        } else {
            temp = head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
        }
        return temp.value;
    }

    @Override
    public T remove(int index) {
        return null;
    }

    @Override
    public List<T> subList(int start, int end) {
        return null;
    }

    @Override
    public void clear() {
        while (last != head) {
            last.next = null;
            last = last.previous;
        }
        head = last = null;
        size = 0;
    }

    @Override
    public int length() {
        return size;
    }

    @Override
    public boolean contains(T element) {
        Node temp = head;
        boolean contains = false;
        while (temp != null) {
            if (element.equals(temp.value)) {
                contains = true;
            }
            temp = temp.next;
        }
        return contains;
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    // 泛型 此处加 T
    private class Itr implements Iterator<T> {

        private Integer index = 0;

        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public T next() {
            return get(index++);
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public T[] toArray(T[] array) {
        if (array.length < size) {
            array = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
        }
        for (int i = 0; i < size; i++) {
            array[ i ] = get(i);
        }
        return array;
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[ size ];
        for (int i = 0; i < size; i++) {
            array[ i ] = get(i);
        }
        return array;
    }
}
